#include <stdio.h>
#define M 100001
int a[M],seq[M],len;
int upper_bound(int i) {
	int l=1,r=len;
	while(l<=r) {
		int m=(l+r)>>1;
		if(seq[l]<=i)l=m+1;
		else r=m-1;
	}
	return l;
}
int main() {
	int n,a,i;
	scanf("%d%d", &n, &a);
	seq[++len]=a;
	for(i = 2; i <= n; i ++) {
		scanf("%d", &a);
		if(seq[len]<a)
			seq[++len]=a;
		else
			seq[upper_bound(a)]=a;
	}
	printf("%d",n-a);
	return 0;
}
